We revisit the classic randomized sketch of a tensor product of $q$ vectors $x_i\in\mathbb{R}^n$.

This work achieves an improved bound on the sample complexity of random tensor projection and it is argued that this bound is tight and nearly optimal. A key observation is to view the random sketch as a bilinear form of a random matrix. It makes the analysis suitable to apply general matrix concentration inequalities. The authors can obtain better bounds by analyzing both operator and Frobenius norm of the random matrix, which is the key challenges of this work. Their proof techniques are different from previous approaches but very impressive.

This paper presents tight bounds on the dimension of random projection for tensor product of vectors, achieving exponential improvement on sketch dimension compared to the prior work. The reviewers found the work solid and of high significance.

We revisit the classic randomized sketch of a tensor product of q vectors x_i\in\mathbb{R} n . However, in their analysis C_{\Omega} 2 can be as large as \Theta(n {2q}), even for a set \Omega of O(1) vectors x . We give a new analysis of this sketch, providing nearly optimal bounds. For the important case of q 2 and \delta 1/\poly(n), this shows that m \Theta(\epsilon {-2} \log(n) \epsilon {-1} \log 2(n)), demonstrating that the \epsilon {-2} and \log 2(n) terms do not multiply each other. In a number of applications, one has \Omega \poly(n) and in this case our bounds are optimal up to a constant factor.

We revisit the classic randomized sketch of a tensor product of $q$ vectors $x_i\in\mathbb{R} n$. However, in their analysis $C_{\Omega} 2$ can be as large as $\Theta(n {2q})$, even for a set $\Omega$ of $O(1)$ vectors $x$. We give a new analysis of this sketch, providing nearly optimal bounds. For the important case of $q 2$ and $\delta 1/\poly(n)$, this shows that $m \Theta(\epsilon {-2} \log(n) \epsilon {-1} \log 2(n))$, demonstrating that the $\epsilon {-2}$ and $\log 2(n)$ terms do not multiply each other. In a number of applications, one has $ \Omega \poly(n)$ and in this case our bounds are optimal up to a constant factor.